BIT Algo/3. Zajęcia/Zadanie 3 (dodatkowe). (Algorytm, który rozstrzyga, czy każda liczba jest sumą 2 innych liczb w tablicy).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaproponować algorytm, który dla tablicy liczb całkowitych rozstrzyga, czy każda liczba z tablicy jest sumą dwóch innych liczb z tej tablicy. Zaproponowany algorytm powinien być możliwe jak najszybszy. Proszę oszacować jego złożoność obliczeniową."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "W pierwszym kroku (jak praktycznie w każdym zadaniu z tej części materiału) należy przesortować tablicę. Ponieważ znów nie wiemy nic na temat wartości, jakie się w niej znajdują, najlepiej posortować tablicę algorytmem Quick Sort (później się okaże, że jego złożoność można pominąć przy obliczaniu złożoności całego algorytmu w notacji dużego O). W kolejnym kroku wystarczy skorzystać z algorytmu, jaki poznaliśmy na 1. ćwiczeniach (patrz Zadanie 7 - szukanie sumy) i dla każej z wartości tablicy sprawdzić, czy istnieją takie dwie liczby, znajdujące się w tej tablicy, że ich suma jest równa tej liczbie."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Oszacowanie złożoności obliczeniowej"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ O(n \\cdot log(n)) $ - sortowanie tablicy algorytmem Quick Sort, <br>\n",
    "$ O(n^2) $ - przechodzenie po wszystkich wartościach i poszukiwanie dla każdej z nich takich dwóch liczb, których suma jest równa tej wartości. <br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### RAZEM:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ O(n \\cdot log(n) + n^2) = O(n^2) $ - sumaryczna złożoność algorytmu w notacji Big O."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_sums(arr):\n",
    "    # Sort an array using Quick Sort algorithm\n",
    "    quick_sort(arr)\n",
    "    # Look for a sum of each value in an array\n",
    "    # We will skip duplicates\n",
    "    prev_val = None\n",
    "    for i in range(len(arr)):\n",
    "        # Skip a value if it was already marked as a sum\n",
    "        # of two values from the array different to this value \n",
    "        if arr[i] != prev_val:\n",
    "            # Return False if found a value which is not a sum\n",
    "            # of two values from the array\n",
    "            if not is_sum_of_two_other_values(arr, i):\n",
    "                return False\n",
    "            prev_val = arr[i]\n",
    "    return True\n",
    "            \n",
    "    \n",
    "def is_sum_of_two_other_values(arr, k):\n",
    "    i = 0\n",
    "    j = len(arr) - 1\n",
    "    \n",
    "    while i < j:\n",
    "        # Skip if i or j is an index of the value checked\n",
    "        if i == k: \n",
    "            i += 1\n",
    "            continue\n",
    "        if j == k: \n",
    "            j -= 1\n",
    "            continue\n",
    "            \n",
    "        curr_sum = arr[i] + arr[j]\n",
    "        if curr_sum < arr[k]: i += 1\n",
    "        elif curr_sum > arr[k]: j -= 1\n",
    "        else: return True\n",
    "        \n",
    "    return False\n",
    "\n",
    "\n",
    "def quick_sort(arr):\n",
    "    _quick_sort(arr, 0, len(arr) - 1)\n",
    "    \n",
    "\n",
    "def _quick_sort(arr, left_idx, right_idx):\n",
    "    while left_idx < right_idx:\n",
    "        pivot_position = _partition(arr, left_idx, right_idx)\n",
    "        \n",
    "        if pivot_position - left_idx < right_idx - pivot_position:\n",
    "            _quick_sort(arr, left_idx, pivot_position)\n",
    "            left_idx = pivot_position + 1  # I removed a tailing recursion\n",
    "        else:\n",
    "            _quick_sort(arr, pivot_position + 1, right_idx)\n",
    "            right_idx = pivot_position  # I removed a tailing recursion\n",
    "        \n",
    "        \n",
    "def _partition(arr, left_idx, right_idx):\n",
    "    pivot = arr[left_idx]\n",
    "    \n",
    "    # Partition an array into 2 subarrays of elements lower than or\n",
    "    # equal to a pivot and of elements greater or equal to a pivot \n",
    "    # (in this partition algorithm pivot isn't placed on a fixed position \n",
    "    # but can be also swapped like all the remaining values)\n",
    "    i = left_idx - 1\n",
    "    j = right_idx + 1\n",
    "    while True:\n",
    "        i += 1\n",
    "        while arr[i] < pivot: i += 1\n",
    "            \n",
    "        j -= 1\n",
    "        while arr[j] > pivot: j -= 1\n",
    "        \n",
    "        if i < j:\n",
    "            _swap(arr, i, j)\n",
    "        else:\n",
    "            return j  # Return a pivot position after the last swap\n",
    "\n",
    "    \n",
    "def _swap(arr, i, j):\n",
    "    arr[i], arr[j] = arr[j], arr[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-8, -4, -2, -2, 2, 2, 8, 9, 14, 14]\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "arr = [random.randint(-15, 15) for _ in range(random.randint(0, 20))]\n",
    "result = check_sums(arr)\n",
    "\n",
    "print(sorted(arr))\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Value: -8  ->\tNone\n",
      "Value: -4  ->\tarr[i] = -2, arr[j] = -2\n",
      "Value: -2  ->\tarr[i] = -4, arr[j] = 2\n",
      "Value: -2  ->\tarr[i] = -4, arr[j] = 2\n",
      "Value: 2  ->\tNone\n",
      "Value: 2  ->\tNone\n",
      "Value: 8  ->\tNone\n",
      "Value: 9  ->\tNone\n",
      "Value: 14  ->\tNone\n",
      "Value: 14  ->\tNone\n"
     ]
    }
   ],
   "source": [
    "def find_sum_indices(arr, target_sum):\n",
    "    i = 0\n",
    "    j = len(arr) - 1\n",
    "    \n",
    "    while i < j:\n",
    "        # Skip if i or j is an index of the value checked\n",
    "        if i == k: \n",
    "            i += 1\n",
    "            continue\n",
    "        if j == k: \n",
    "            j -= 1\n",
    "            continue\n",
    "        \n",
    "        curr_sum = arr[i] + arr[j]\n",
    "        if curr_sum == target_sum: return i, j\n",
    "        if curr_sum < target_sum: i += 1\n",
    "        else: j -= 1\n",
    "            \n",
    "    return None, None\n",
    "\n",
    "for k in range(len(arr)):\n",
    "    i, j = find_sum_indices(arr, arr[k])\n",
    "    print('Value:', arr[k], end='  ->\\t')\n",
    "    print(f'arr[i] = {arr[i]}, arr[j] = {arr[j]}' if i is not None else None)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}